package fun.coding.leetcode;

public class JumpGameII {

	public static void main(String[] args) {
		JumpGameII ins = new JumpGameII();

		int[] test1 = {2, 3, 1, 1, 4};
		System.out.println(ins.jump(test1));
	}
	
	
	/***
	 * http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html
	 * http://xlagrange.github.io/code/2014/02/06/leetcode.html 
	 */
	
	public int jump(int[] A) {
		// Can't handle the 1 case
		if (A == null || A.length <= 1) return 0;
		
		int left = 0;
		int right = 0;
		int count = 0;
		
		while (right < A.length) {
			int farReach = 0;
			count++;
			
			for (int i = left; i <= right; i++) {
				if (A[i] + i >= A.length - 1) {
					return count;
				}
				
				farReach = Math.max(A[i] + i, farReach);
			}
			
			left = right + 1;
			right = farReach;
		}
		return count;
	}
	
	// This is O(N^2), TLE
	public int jumpDp(int[] A) {
		if (A == null || A.length == 0) return 0;
		
		int[] lookup = new int[A.length];
		lookup[0] = 0;
		
		for (int i = 1; i < A.length; i++) {
			int min = Integer.MAX_VALUE;
			for (int j = i - 1; j >= 0; j--) {
				if (A[j] >= i - j) {
					min = Math.min(min, lookup[j] + 1);
				}
			}
			lookup[i] = min;
		}
		
		return lookup[A.length - 1];
	}
}
